package com.zwy.leetcode;

import java.util.*;

public class CombinationTest {
    /**
     * 77. 组合
     * @param n
     * @param k
     * @return
     */
    List<List<Integer>>res=new LinkedList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        LinkedList<Integer>list=new LinkedList<Integer>();
        if(k==1) {
            for (int i = 1; i <=n; i++) {
                LinkedList<Integer>list0=new LinkedList<Integer>();
                list0.add(i);
                res.add(list0);
            }
            return res;
        }
        backTrack(n,k,list);
        return res;
    }
    public void backTrack(int n,int k,LinkedList<Integer> list){
        if(list.size()==k){
            boolean flag=true;
            for (int i = 1; i < list.size(); i++) {
                if(list.get(i-1)>list.get(i))flag=false;
            }
            if(flag)
            res.add(new LinkedList(list));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if(list.contains(i))
                continue;
            if(list.size()>0){
                if(list.get(list.size()-1)>i)continue;
            }
            list.add(i);
            backTrack(n,k,list);
            list.removeLast();
        }
    }

    /**
     * 784. 字母大小写全排列
     * @param s
     * @return
     */
    List<String>list=new LinkedList<String>();
    public List<String> letterCasePermutation(String s) {
        char[] chars = s.toCharArray();
        LinkedList<Integer>list0=new LinkedList<Integer>();
        backTrack0(chars,s.length(),list0);
        return list;
    }
    public void backTrack0(char[] chars,int n,LinkedList<Integer>list0){
        if(chars.length==n){
            list.add(chars.toString());
            return;
        }
        for (int i = 0; i <n ; i++) {
            if(list.contains(i))continue;
            list0.add(i);
//            if(chars[i]>=97&&chars[i]<=122)
//            chars[i]-=32;
            backTrack0(chars,n,list0);
            list0.removeLast();
        }
    }

    List<List<Integer>> res1=new LinkedList<List<Integer>>();
    int count=0;
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length<3)return res1;
        Arrays.sort(nums);
        LinkedList list=new LinkedList<Integer>();
        backTrack(nums,list,0);
        return  res1;
    }
    public void backTrack(int []nums,LinkedList<Integer>list,int start){
        if(list.size()==3){
            if(count==0)
                res1.add(new LinkedList<>(list));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if(nums.length - i  < 3 - list.size())return;
            if(start != i && nums[i - 1] == nums[i])continue;
            if(i < nums.length - 1 && count + nums[i] + (2 - list.size()) * nums[i + 1] > 0)return;
            if(i < nums.length - 1 && count + nums[i] + (2 - list.size()) * nums[nums.length - 1] < 0)continue;
            count += nums[i];
            list.add(nums[i]);
            backTrack(nums,list,i+1);
            list.removeLast();
            count-=nums[i];
        }
    }

    public static void main(String[] args) {
        int []arr={
                -1,0,1,2,-1,-4};
        CombinationTest test=new CombinationTest();
        List<List<Integer>> lists = test.threeSum(arr);
        System.out.println(lists);
    }
}
